#include "quicksort.h"
#include "huff.h"

void swap(Node *a, Node *b)
{
  Node t;
  t.value = a->value; t.prob = a->prob;  t.next = a->next;
  a->value = b->value; a->prob = b->prob;  a->next = b->next;
  b->value = t.value; b->prob = t.prob; b->next = t.next;
}

void sort(Node* arr, int beg, int end)
{
  if (end > beg + 1)
  {
    Node piv = arr[beg];
    int l = beg + 1, r = end;
    while (l < r)
    {
      if (arr[l].prob <= piv.prob)
        l++;
      else
        swap(arr+l, arr+(--r));
    }
    swap(arr+(--l), arr+beg);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}

